Algorithm Alley
by Jon Bentley 


Example 1:
(a)
maxlen = -1
for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        thislen = comlen(&c[i], &c[j])
        if thislen > maxlen
            maxlen = thislen

            maxi = i
            maxj = j

(b)
int comlen(char *p, char *q)
    i = 0
    while *p && (*p++ == *q++)
        i++
    return i

(c)
#define MAXN 5000000
char c[MAXN], *a[MAXN];

(d)
while (ch = getchar()) != EOF
    a[n] = &c[n]
    c[n++] = ch
c[n] = 0

(e)
qsort(a, n, sizeof(char *), pstrcmp)

(f)
for (i = 0; i < n; i++)
    if comlen(a[i], a[i+1]) > maxlen
        maxlen = comlen(a[i], a[i+1])
        maxi = i
printf("%.*s\en", maxlen, a[maxi])


Example 2:
(a)
int k = 2;
char inputchars[5000000];
char *word[1000000];
int nword = 0;

(b)
word[0] = inputchars
while scanf("%s", word[nword]) != EOF
    word[nword+1] =
        word[nword] + strlen(word[nword]) + 1
    nword++

(c)
int wordncmp(char *p, char* q)
    n = k
    for ( ; *p == *q; p++, q++)
        if (*p == 0 && --n == 0)
            return 0
    return *p - *q

(d)
for (i = 0; i < k; i++)
    word[nword][i] = 0
for (i = 0; i < k; i++)
    print word[i]
qsort(word, nword, sizeof(word[0]), sortcmp)

Example 3:
phrase = first phrase in input array
loop
    binary search for phrase in word[0..nword-1]
    for all phrases equal in the first k words
        select one at random, pointed to by p
    phrase = word following p
    if k-th word of phrase is length 0
        break
    print k-th word of phrase


Example 4:
phrase = inputchars
for (words = 10000; words > 0; words--)
    l = -1
    u = nword
    while l+1 != u
        m = (l + u) / 2
        if wordncmp(word[m], phrase) < 0
            l = m
        else
            u = m
    for (i = 0; wordncmp(phrase, word[u+i]) == 0; i++)
        if rand() % (i+1) == 0
            p = word[u+i]
    phrase = skip(p, 1)
    if strlen(skip(phrase, k-1)) == 0
        break
    print skip(phrase, k-1)


Listing One
/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */
/* longdup.c -- Print longest string duplicated M times */

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

int pstrcmp(char **p, char **q)
{   return strcmp(*p, *q); }

int comlen(char *p, char *q)
{   int i = 0;
    while (*p && (*p++ == *q++))
        i++;
    return i;
}
#define M 1
#define MAXN 5000000
char c[MAXN], *a[MAXN];

int main()
{   int i, ch, n = 0, maxi, maxlen = -1;
    while ((ch = getchar()) != EOF) {
        a[n] = &c[n];
        c[n++] = ch;
    }
    c[n] = 0;
    qsort(a, n, sizeof(char *), pstrcmp);
    for (i = 0; i < n-M; i++)
        if (comlen(a[i], a[i+M]) > maxlen) {
            maxlen = comlen(a[i], a[i+M]);
            maxi = i;
        }
    printf("%.*s\n", maxlen, a[maxi]);
    return 0;
}

Listing Two
/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */
/* markov.c -- generate random text from input document */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


char inputchars[4300000];
char *word[800000];
int nword = 0;
int k = 2;

int wordncmp(char *p, char* q)
{   int n = k;
    for ( ; *p == *q; p++, q++)
        if (*p == 0 && --n == 0)
            return 0;
    return *p - *q;
}
int sortcmp(char **p, char **q)
{   return wordncmp(*p, *q);
}
char *skip(char *p, int n)
{   for ( ; n > 0; p++)
        if (*p == 0)
            n--;
    return p;
}
int main()
{   int i, wordsleft = 10000, l, m, u;
    char *phrase, *p;
    word[0] = inputchars;
    while (scanf("%s", word[nword]) != EOF) {
        word[nword+1] = word[nword] + strlen(word[nword]) + 1;
        nword++;
    }
    for (i = 0; i < k; i++)
        word[nword][i] = 0;
    for (i = 0; i < k; i++)
        printf("%s\n", word[i]);
    qsort(word, nword, sizeof(word[0]), sortcmp);
    phrase = inputchars;
    for ( ; wordsleft > 0; wordsleft--) {
        l = -1;
        u = nword;
        while (l+1 != u) {
            m = (l + u) / 2;
            if (wordncmp(word[m], phrase) < 0)
                l = m;
            else
                u = m;
        }
        for (i = 0; wordncmp(phrase, word[u+i]) == 0; i++)
            if (rand() % (i+1) == 0)
                p = word[u+i];
        phrase = skip(p, 1);
        if (strlen(skip(phrase, k-1)) == 0)
            break;
        printf("%s\n", skip(phrase, k-1));
    }
    return 0;

}





4